Graphs: Introduction

Overview#

A graph is a nonlinear data structure that consists of vertices, $V$, and edges, $E$. Vertices, also called nodes, can represent any data, and edges are the lines that connect two vertices in the graph. A graph can be represented as $G(V, E)$, where $V$ represents vertices, and $E$ represents edges. An edge connecting $u$ and $v$, such that ${u, v}\in V$, is represented by a pair of vertices denoted as $(u, v)$.

Here, $u$ and $v$ are the vertices that are connected by that edge.

There are various types of graphs:

• Undirected graph: A graph in which the edges have no direction, and the relationship between vertices is two way.
• Directed graph: A graph in which the edges have a direction, meaning the relationship between vertices is one way.
• Weighted graph: A graph in which each edge has a numerical weight. This numerical weight can represent the length, cost, or some other attribute of the edge.
• Cyclic graph: A graph that contains at least one cycle, meaning that there is a path that starts and ends at the same vertex.
• Acyclic graph: A graph that contains no cycles, meaning that no path starts and ends at the same vertex.

Graph representation#

Graphs are usually represented as either an adjacency list or an adjacency matrix in order to solve graph-related problems.

An adjacency list is a collection of lists where each list represents a vertex of the graph. Each list within the adjacency list contains vertices that are directly connected with a particular vertex. In the case of weighted graphs, the weight is stored along with the vertex; otherwise, it is considered as $1$ and usually omitted from the lists.

An adjacency matrix is a 2D array where the row $i$ and column $j$ represent the graph’s vertices. If there is an edge between vertex $i$ and vertex $j$, the element $(i,j)$ of the matrix will be $1$ in the case of an unweighted graph. It will be the weight of the edge in the case of a weighted graph. If there is no connection between the two vertices, the value $(i,j)$ will be $0$.

BFS and DFS#

Breadth-first search (BFS) is an algorithm to traverse different vertices in breadth-first order. The algorithm starts by traversing the source vertex and adding it to the list of vertices to visit. The algorithm removes the inserted vertex, marks it as visited, and inserts all its neighbors into the list. This node has now been fully explored. The algorithm moves on to the next vertex in the list. The algorithm continues this process until there are no more vertices left to traverse in the list.

The following illustration shows how a BFS works on a graph discussed above:

Depth-first search (DFS) is an algorithm to traverse different vertices in depth-first order. The algorithm starts with a source vertex and visits one of its neighbors. From there, it visits one of its neighbors and repeats the process until we reach a vertex with no unvisited neighbors. Then, we backtrack to the previous vertex and visit its other unvisited neighbors. We continue this process until we have visited all the vertices in the graph that are reachable from the starting vertex.

The following illustration shows how a DFS works on a graph discussed above:

In solving a graph-related problem, there is always a choice to select the suitable algorithm according to the nature of the given problem. The choice depends on the specific requirements of the problem being solved, and the optimal choice may vary based on the size and structure of the graph, the specific constraints of the problem, and other factors. For example, BFS is a good choice for finding the shortest path in an unweighted graph because it brings up the best possible solution at a particular vertex before moving forward. It visits all vertices at a given distance from the source vertex before visiting vertices farther away. DFS, on the other hand, is a good choice to find a path in a maze when you want to explore vertices that are far away from the source vertex before visiting vertices that are closer. This makes DFS a good choice for problems that require the traversal of deep branches of the graph.

Prim’s algorithm finds the minimum spanning tree of a weighted graph by starting from any vertex and then iteratively adding the minimum-weight edge that connects a vertex in the current tree to a vertex outside the tree until all vertices are included in the tree. Dijkstra’s algorithm finds the shortest path between a source vertex and all other vertices in a weighted graph by visiting vertices in order of increasing distance from the source vertex. It also updates the distances to neighboring vertices and chooses the next vertex with the smallest distance until all vertices are visited.

Examples#

The following examples illustrate some problems that can be solved with these approaches:

Does my problem match this pattern?#

• Yes, if the following condition is fulfilled:

  • There is a network of interconnected objects with some relationship between them; that is, the data can be represented as a graph.

• No, if the following condition is fulfilled:

  • The problem does not involve a set of objects and their relationships; that is, the data cannot be represented as a graph.

Real-world problems#

Many problems in the real world use the graphs pattern. Let’s look at some examples.

• Routing of IP packets on the internet: The internet can be modeled as a graph, where vertices represent routers, and edges represent the connections between them. The edges can have various weights that represent the cost of sending a packet from one router to another. The goal of the routing algorithms is to find the shortest path between the source and destination routers for each packet and to deliver it as soon as possible.

• Flight route optimization: Airlines use graph-based algorithms to optimize flight routes. The airport network can be represented as a graph, where vertices represent airports, and edges represent flights connecting them. The algorithms can be used to find the shortest route between two airports, reduce fuel consumption, and minimize flight time.

• Detecting deadlocks in operating system processes: Processes in the operating system can be modeled as vertices in a graph, and the resources they hold and need can be modeled as edges in the graph. A cycle in the graph indicates that there is a set of processes that are waiting for each other and, therefore, are in a deadlock. To detect deadlocks, the operating system maintains the resource allocation graph and periodically checks for cycles using graph-based algorithms.

Strategy time!#

Match the problems that can be solved using the graphs pattern.

Note: Select a problem in the left-hand column by clicking on it, and then click on one of the two options in the right-hand column.